#include<vector>
#include<iostream>
using namespace std;


void dfs(vector<int>& x, vector<int>& y, vector<int>& z, int n)
{
    if (n == 1)
    {
        z.push_back(x.back());
        x.pop_back();
        return;
    }

    dfs(x, z, y, n - 1);
    z.push_back(x.back());
    x.pop_back();
    dfs(y, x, z, n - 1);
}

void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
    int n = A.size();
    dfs(A, B, C, n);
    for (auto x : C)
        cout << x;
}

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};

ListNode* dfs(ListNode* list1, ListNode* list2)
{
    if (list1 == nullptr)
        return list2;
    if (list2 == nullptr)
        return list1;
    if (list1->val > list2->val)
    {
        list2->next = dfs(list1, list2->next);
        return list2;
    }
    else
    {
        list1->next = dfs(list1->next, list2);
        return list1;
    }
}

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    return dfs(list1, list2);
}

int main()
{
    vector<int> x{ 2,1,0 }, y, z;
    hanota(x, y, z);


	return 0;
}